Currently, asynchronous transfer mode (ATM) networks are becoming more and more commonplace in environments that require high speed data networking and switching facilities. ATM's small cell size of 53 bytes facilitates very fast hardware switch fabrics. ATM is suitable for fast switching of any type data source such as data, video, audio, etc.
For an application to transmit data onto an ATM network it is required to segment that data into 53 byte cells. This may be done in either hardware or in software, in the case of slower communication lines. In many instances, end users of the ATM network maintain contractual agreements with the ATM service provider. Typically, as part of these contractual agreements, applications are expected to be restricted in the average rate (i.e., speed) of data that may be generated and transmitted. In addition, applications may be allocated a certain number of cells that may be transmitted at a higher (e.g., burst) rate.
The average data rate allocated by any network should not exceed its operating capacity. The maximum burst rate is required in order to put a limit on the amount of bandwidth consumed by applications that may exceed this capacity. Another parameter critical to an application's configuration is the variance or delay between successive cells. This is called the cell delay variance (CDV). The CDV is a measure of the changes in delay experienced by other applications sharing the same ATM line. The CDV is required since multiple connections on the same line compete against each other for bandwidth. If one application is allowed to burst for a long period of time, it may starve other applications for bandwidth until it completes its transmission. For many types of applications (e.g., voice) it is critical that the longest delay between transmission slots be known. The longest delay can be guaranteed only if the maximum burst of each application is limited to a known value.
Since ATM data traffic is transmitted in 53 byte cells, which at ATM data rates is a relatively very short time, traffic pattern calculations (i.e., usage and burst) need to be very efficient. For example, at a data rate of only 2 Mbps, traffic pattern calculations must be made approximately every 220 microseconds, which is the time for the transmission of a single cell. At much higher data rates, such as 155 Mbps and 625 Mbps, the time for traffic pattern calculations decreases substantially.
Proposed algorithms for enforcing transmission rates are based on what is called a leaky bucket algorithm. Using this algorithm, data is stored in a buffer and the buffer is depleted at given time intervals. Most implementations of this algorithm require the controller that is managing the process to check the buffer at very close time intervals that are based on the time taken to transmit a single cell. It also requires the controller to calculate the precise time at which the next cell will be transmitted over the connection and only allow the cell to be transmitted at that particular time. Carrying out this requirement often involves numerous calculations which include multiplications and divisions. These are time consuming to carry out, especially in the case, for example, when bandwidth is not evenly divided. For example, one application connection may have 17% of the total bandwidth allocated to it and another application connection may have 23% allocated, etc. Calculating the precise time for next cell transmission in either case will require multiplication and division of the cell time interval.